#include"monkeyking.h"
#include<stdlib.h>
#include<conio.h>
#include<stdio.h>
//创建单循环链表
//定义结构体类型，用于创建循环链表
//typedef struct Cnode
//{
//	int data;
//	struct Cnode* next;
//}CNode;
int Create_clist(CNode* clist, int n)
{
	CNode* p, * q;
	int i;
	clist = (CNode*)malloc(sizeof(CNode));//开辟第一个结点
	clist->data = 1;
	clist->next = NULL;
	q = clist;//使用q来保存第一个结点
	for (i = 2; i <= n; i++)//尾插链表
	{
		p = (CNode*)malloc(sizeof(CNode));//每次开辟一个新节点
		if (p == NULL)//如果申请内存不成功
			return -1;
		//申请成功的赋值操作
		//clist = p;
		p->data = i;//赋值给每个结构体
		clist->next = p;//让p指向clist
		clist = p;//每次clist都等于最新创建的结点，整体循环结束后就是最前面的结点
		/*if (i == n)
			q = p;//利用q来暂存p的数据*/
	}
	clist->next = q;//让尾部指向头部
	monkeyjoseph = q;//把头指针赋值给monkeyjoseph
	//for (i = 0; i < 13; i++)
	//{ 
	//	printf("%5d", q->data);
	//	q = q ->next;
	//}
	return 1;
}
//创建约瑟夫环
int Joseph(CNode* clist, int m, int n, int k)
{
	int i, temp, x = 0, king = 1;
	CNode* p, * q;
	temp = k;
	if (m > n)//报数位置不正确
		return -1;
	if (!Create_clist(clist, n))//创建链表不成功
		return -1;
	p = monkeyjoseph;
	for (i = 1; i < m; i++)
		p = p->next;
	while (p)
	{
		for (i = 1; i < k - 1; i++)//移动的p应该比报数少一
			p = p->next;
		q = p->next;//q用来存储p的下一个数据，好实现报数猴子的删除操作
		printf("%-5d", q->data);
		
		x++;
		if (x == 15)
		{
			printf("\n");
			x = 0;
		}//规整输出格式
		
		if (p->next == p) //如果到了最后一个数据出列，证明此数是猴王编号
		{
			king = p->data;
			p = NULL;
		}
		else 
		{
			p->next = q->next;//q的next是p的next的next
			p = p->next;
			free(q);
		}
		if (k != 0)
			k--;
		else
			k = temp;
	}
	clist = NULL;
	return king;//返回最后报数的猴子位置
}
